
	/**************************************** 
	*  Submitted by:                        *   
	*                                       *
	*  Michael Fildstein, ID: 309161594     *  
	*  Tomer Ben Rachel, ID: 021982475      *
	*   					*
	*****************************************/  




public class Knapsack3 {
 

	//This program attempts to place a certain number of different smaller rectangles into a bigger rectangle, thus filling it up
	//If we can do this, even if we don't fill up all of the space, the program returns the rectangle filled up with the smaller rectangles
	//Otherwise, the program returns a null matrix.

	 
	   //iWidth - the width of the knapsack
	   //iHeight - the height of the knapsack
	   //aiRectangles[i][0] - the width of the i'th rectangle
	   //aiRectangles[i][1] - the height of the i'th rectangle
	   public static int[][] insertIntoKnapsack( int iWidth, int iHeight, int[][] aiRectangles ){
	    int[][] aiKnapsack = new int[iWidth][iHeight];
	    if(insertIntoKnapsack(aiKnapsack, aiRectangles, 0))
	    	return aiKnapsack;
	    return null;
	   }


	  //The recursive function insertIntoKnapsack tries to insert the current rectangle into the knapsack
	  //Returns true on success and false on failure 
	   public static boolean insertIntoKnapsack( int[][] aiKnapsack, int[][] aiRectangles, int iCurrent ){
	    boolean ans = false;
	    boolean checkInput = inputCheck(aiKnapsack, aiRectangles);
	    int[] coordinates = {0,0};                                          //Those are the starting coordinates (top left corner) of the knapsack.
	    
	    if(checkInput){
	        int[] usedShape = new int[aiRectangles.length];                     //An array that keeps track of the shapes already used.
		    int[][] solution = new int[aiKnapsack.length][aiKnapsack[0].length];  
		    

		   //This part checks if the Area of all the rectangles and the area of the knapsack is equal
		   //if the areas are not equal, it is not possible to fit the rectangles inside the knapsack
		    
		    int knapsackArea = aiKnapsack.length * aiKnapsack[0].length;    
		    int rectanglesArea = rectanglesArea(aiRectangles);    
		    if (knapsackArea > rectanglesArea){
		    	ans = insertIntoKnapsack(aiKnapsack, aiRectangles, iCurrent , coordinates , usedShape ,solution , false);
		    	voidCopy2DArray(solution, aiKnapsack);
		    	}
		    if (knapsackArea == rectanglesArea){
		    	ans = insertIntoKnapsack(aiKnapsack, aiRectangles, iCurrent , coordinates , usedShape ,solution , true);
		    	voidCopy2DArray(solution, aiKnapsack);
		    	}
	    }
	    
	
	   return ans;
	   }
	   
	   
	//The function insertIntoKnapsack returns true if there is a way we can insert all the smaller rectangles into the Knapsack
	//Otherwise returns false

	   public static boolean insertIntoKnapsack( int[][] aiKnapsack, int[][] aiRectangles, int iCurrent, int[] coordinates , int[] usedShape ,int [][] solution , boolean equalArea){
	    
	    System.out.println("*****************************");  //should not be in the final version.
	    System.out.println(getKnapsackString(aiKnapsack));
	    System.out.println("*****************************");
	    

	//The next two matrices, tempUsedShape and tempKnapsack, are used to store the current
	//set up of the rectangles inside the Knapsack and which rectangles we have used in each
	//iteration of the function
	    int [] tempUsedShape = new int[usedShape.length];       
	    int[][] tempKnapsack = deepCopy2DArray(aiKnapsack);

	//Calls to the allShapesBeenChecked function to see if we have tried to insert all smaller rectangles in a certain place
	    boolean allShapesBeenChecked = allShapesBeenChecked(usedShape);
	//Calls to the globalCanFit function to see if we can still place our unused rectangles somewhere in the Knapsack
	    boolean globalCanFit = globalCanFit(aiKnapsack, aiRectangles, usedShape);
	    if (iCurrent == aiRectangles.length){          //if we reached the end of aiRectangles, we should go back to the first shape.
	     return insertIntoKnapsack(aiKnapsack, aiRectangles, 0, coordinates, usedShape ,solution,equalArea);
	    }

	    if(allShapesBeenUsed(usedShape)){        //if the board is full this means we found our solution
	     voidCopy2DArray(aiKnapsack, solution);
	     return true;
	    }
	    
	    if (!globalCanFit && !equalArea){     //If we can't place any of our unused rectangles in the Knapsack and the area of the Knapsack is bigger than the area
	     return false;                                  //of all the rectangles, this means there is no solution for this iteration
	    }
	    
	 //checks if it possible to fit *any* of the yet unused shapes in the current coordinate.
	    boolean noShapeCanFit = noShapeCanFit(aiKnapsack, aiRectangles, coordinates, usedShape);
	    int [] newCoordinates = advanceCoordinates(coordinates, aiKnapsack);  //The coordinates of the next cell.
	   

	//If we can place any of our unused rectangles in the Knapsack and the area of the Knapsack is bigger than the area
	// Of all the rectangles and not any one of our rectangles can fit in the coordinate we are at, and that coordinate is at the end of the matirx
	//We need to start from the beginning of the matirx
	  
	 
	    if(globalCanFit  &&  noShapeCanFit && !equalArea){
	     if (coordinates[0] != -1){
	      return insertIntoKnapsack(aiKnapsack, aiRectangles, iCurrent, newCoordinates, usedShape ,solution ,equalArea);
	     }else{
	//Meaning that the area of the Knapsack is equal to the area of all the rectangles, then there is no solution
	      return false;
	     }
	    
	   }
	    
	    if(coordinates[0] == - 1){ //if we reached to the end of the board , we should start from (0,0) again.
	     if (allShapesBeenChecked){         //If we tried to place all the rectangles, there is no solution for this iteration
	      return false;
	     }else{
	      int[] startCoordinates = new int[2];  //Otherwise, start from the beginning of the Knapsack
	      return insertIntoKnapsack(aiKnapsack, aiRectangles, iCurrent, startCoordinates, usedShape ,solution,equalArea);
	     }
	      
	     
	    }
//	    boolean noShapeCanFit = noShapeCanFit(aiKnapsack, aiRectangles, coordinates, usedShape); //checks if it possible to fit *any* of the yet unused shapes in the current coordinate.
	    boolean canFit = canFit(aiKnapsack, aiRectangles, coordinates, iCurrent); //checks if it is possible to fit the current shape in the current coordinate.
	    
	    deepCopy1DArray(usedShape,tempUsedShape);
	    
	    
	    
	    if (aiKnapsack[coordinates[1]][coordinates[0]] != 0){    //if another shape already occupies the current coordinate , we move to the next coordinate.
	     return insertIntoKnapsack(aiKnapsack, aiRectangles, iCurrent, newCoordinates, usedShape ,solution ,equalArea);
	    }
	    
	    
	    
	    
	    if (noShapeCanFit && equalArea){        //if it is impossible to fit any of the yet unused shapes into the current coordinate  
	     voidCopy2DArray(aiKnapsack, solution);   //this means it is impossible to fill the knapsack.
	     return false;
	    }
	    
	    
	    if (usedShape[iCurrent] == 1){      //if we already used the current shape , we should move to the next one.
	     return insertIntoKnapsack(aiKnapsack, aiRectangles, iCurrent + 1, coordinates, usedShape,solution,equalArea);
	    }
	    
	    if (canFit){          //if it is possible to fit the current shape.
	     tempUsedShape[iCurrent ]= 1;
	     insertRactangle(aiKnapsack, aiRectangles, coordinates, iCurrent); 
	     
	     
	     return insertIntoKnapsack(aiKnapsack, aiRectangles, iCurrent + 1, newCoordinates, tempUsedShape ,solution,equalArea) ||  //SUSU - we insert the current shape, or we move the current shape to the next coordinate.
	         insertIntoKnapsack(tempKnapsack, aiRectangles, iCurrent, newCoordinates, usedShape,solution,equalArea);
	     
	     
	    }else{
	     return insertIntoKnapsack(aiKnapsack, aiRectangles, iCurrent + 1, coordinates , usedShape ,solution, equalArea);  //if it is impossible to fit the current shape we move to the next one.
	    }
	    
	    
	   }
	   
	   
	   //Additional functions:

	//The function inputCheck purpose is to verify if the input to the program is correct and legitimate
	//If the input is incorrect, the function returns false. Otherwise, it returns true   
	 public static boolean inputCheck(int [][] aiKnapsack , int [][] aiRectangles ){
		 boolean ans=true;
		 if(aiKnapsack == null || aiRectangles == null)
			 ans=false;
		 else
		 	{for(int i = 0; i < aiKnapsack.length && ans; i++){
		 		if(aiKnapsack[i] == null) ans=false;
		 		}
		 	 for(int j=0; j < aiRectangles.length && ans; j++ ){
		 		 if(aiRectangles[j] == null || aiRectangles[j][0]<0 || aiRectangles[j][1]<0)
		 			 ans=false;
		 		 
		 	 	}
		    }
		 return ans;
	 }
	   
	   
	   
	//The function globalCanFit receives three matrices, representing the Knapsack, the rectangles and the rectangles we used
	//And checks if we can place any rectangle we haven't used yet somewhere in the Knapsack.
	//If we can, the function returns true, else false.

	   public static boolean globalCanFit (int [][] aiKnapsack , int [][] aiRectangles , int []usedShape){
	    boolean ans = false;
	    int [] coordinates = new int [2];
	    
	    while (coordinates[0] != -1 && !ans){
	     if (!noShapeCanFit(aiKnapsack, aiRectangles, coordinates, usedShape)){
	      ans = true;
	     }else{
	     coordinates = advanceCoordinates(coordinates, aiKnapsack);
	     }
	    }
	    return ans;
	   }
	    
	   //The function rectanglesArea calculates the total area of all  the rectangle in a given rectangles array and
	  //Returns that sum.
	   public static int rectanglesArea (int [][] aiRectangles){  
	    int ans = 0;
	    for (int i = 0 ; i < aiRectangles.length ; i++){
	     ans = ans + (aiRectangles[i][0] * aiRectangles[i][1]); 
	    }
	    return ans;
	   }
	   


	   //The function allShapesBeenUsed checks if all the shapes have been used.
	  //Returns true if they have, otherwise, false.
	   public static boolean allShapesBeenUsed (int [] usedShape){  
	    boolean ans = true; 
	    for (int i = 0 ; i < usedShape.length && ans; i++ ){
	     if (usedShape[i] != 1){
	      ans = false;
	     }
	    }
	    return ans;
	    
	   }


	   //The function allShapesBeenChecked checks if all the shapes have been checked. Meaning, we have tried to place shapes, even if they didn't fit
	  //Returns true if that is the case, otherwise, false.
	   public static boolean allShapesBeenChecked (int [] usedShape){  
	    boolean ans = true; 
	    for (int i = 0 ; i < usedShape.length && ans; i++ ){
	     if (usedShape[i] != 1){
	      ans = false;
	     }
	    }
	    return ans;
	    
	   }
	   
	   
	   //The function noShapeCanFit  checks if it is possible to fit any of the still unused shapes inside the given coordinate.
	   //Returns true if no rectangle can fit, otherwise false.
	   public static boolean noShapeCanFit(int [][] aiKnapsack ,int [][]aiRectangles , int[] coordinates , int[] usedShape){
	    boolean ans = true;
	    if ( coordinates[0] != - 1){ 
	     for (int i = 0 ; i < aiRectangles.length && ans ; i++){
	      if (usedShape[i] != 1){
	       if(canFit(aiKnapsack, aiRectangles, coordinates, i)){
	        ans = false;
	       }
	      }
	     }
	    } 
	    return ans;
	   }
	   
	   
	   
	   // deepCopy1darray deep copies a1 into a2.
	   public static void deepCopy1DArray (int[] a1, int[] a2){
		   for (int i = 0 ; i < a1.length ; i++){
			   a2[i] = a1[i];
		   }
	   }

	   
	   
	   
	   //The function deepcopy2dArray ﻿deep copies the knapsack

	   public static int[][] deepCopy2DArray (int[][] aiKnapsack){     
	    int [][] knapSackTemp = new int[aiKnapsack.length][aiKnapsack[0].length];
	    for (int i = 0 ; i < aiKnapsack.length ; i++){
	     for (int j = 0 ; j < aiKnapsack[i].length ; j++){
	      knapSackTemp[i][j] = aiKnapsack[i][j];
	     }
	    }
	    return knapSackTemp;
	   }


	   //Void copy 2dArray
	   //Same as the above function , only it does not create a new array.
	   public static void voidCopy2DArray (int[][] aiKnapsack , int[][] solution){     //deep copies the knapsack
	    for (int i = 0 ; i < aiKnapsack.length ; i++){
	    	for (int j = 0 ; j < aiKnapsack[i].length ; j++){
	      		solution[i][j] = aiKnapsack[i][j];
	     	}
	    }
	    
	   }
	   
	   
	   
	   
	   //The function advanceCoordinates advances a given coordinates by  1 unit. if reaches the end returns (-1,-1)
	   //Returns the array coordinates after the advancement
	   public static int[] advanceCoordinates (int[] coordinates , int [][] aiKnapsack){ 
	    int x = coordinates[0];
	    int y = coordinates[1];
	    int[] newCoordinates = new int[2];
	    newCoordinates[0] = coordinates[0];
	    newCoordinates[1] = coordinates[1];
	    
	    if (x < aiKnapsack[0].length - 1 ){  //If we haven't reached the rightmost cell of the row
	     newCoordinates[0] = x + 1;
	    }
	    if (x == aiKnapsack[0].length - 1){  //If we have reached the rightmost cell of the row
	     if (y < aiKnapsack.length - 1){         //And we haven't reached the bottom right corner
	      newCoordinates[0] = 0 ;        //We need to go down a row
	      newCoordinates[1] = y + 1;
	     }
	     if (y == aiKnapsack.length - 1){        //If we are at the bottom right corner
	      newCoordinates[0] = -1;
	      newCoordinates[1] = -1;
	     }
	    }
	    return newCoordinates ;
	   }
	   
	   
	   //The function canFit checks if a given shape can fit in a given coordinate inside the knapsack
	   //Retuns true if it can fit, otherwise, false
	   public static boolean canFit (int [][] aiKnapsack , int[][] aiRectangles, int[] coordinates , int iCurrent){   
	    boolean yOk =false;
	    boolean xOk = false;                         
	    boolean meetCondition = true;
	    int xCoordinate = coordinates[0];
	    int yCoordinate = coordinates[1];
	    int height = aiRectangles[iCurrent][0];
	    int length = aiRectangles[iCurrent][1];
	    if (aiKnapsack[yCoordinate][xCoordinate] == 0){
	     for (int y = yCoordinate ; y < (yCoordinate + height) && y < aiKnapsack.length && meetCondition; y++){
	      if (y == yCoordinate + height - 1){
	       yOk =true;
	      }
	      for (int x = xCoordinate ; x < xCoordinate + length && x < aiKnapsack[y].length && meetCondition  ; x ++){
	       if (aiKnapsack[y][x] == 0 && x == (xCoordinate + length - 1)){
	        xOk = true;
	       }
	       if (aiKnapsack[y][x] != 0){
	        xOk = false;
	        meetCondition = false;
	       }
	       
	      }
	     }
	    } 
	    return xOk && yOk;
	   } 
	   
	   
	   //The function insertRectangle inserts a given shape in the given coordinate inside the knapsack

	   public static void insertRactangle (int [][] aiKnapsack , int[][] aiRectangles, int[] coordinates , int iCurrent){ 
	    if (canFit(aiKnapsack, aiRectangles, coordinates, iCurrent)){   //possibly not so smart check , consider removing for optimization.             
	     int xCoordinate = coordinates[0];                     
	     int yCoordinate = coordinates[1];
	     int height = aiRectangles[iCurrent][0];
	     int length = aiRectangles[iCurrent][1];
	     
	     for (int y = yCoordinate ; y < yCoordinate + height ; y++){
	      for (int x = xCoordinate ; x < xCoordinate + length ; x++){
	       aiKnapsack[y][x] = iCurrent + 1;
	      }
	     }
	    } 
	   }
	   
	   // arrayToString
	   public static String arrayToString (int[] array){
	    String a1 = "" + array[0];
	    for (int i = 1 ; i < array.length ; i++){
	     a1 = a1 +','+ array[i];
	    }
	    return a1;
	   }
	   
	   
	   //End  Of My code.s   
	   public static String getKnapsackString( int[][] aiKnapsack ){
	    int cRows = aiKnapsack.length;
	    int cCols = aiKnapsack[0].length;
	    int iRow = 0, iCol = 0;
	    String sOutput = "";
	    for( iRow = 0 ; iRow < cRows ; iRow++ ){
	     for( iCol = 0 ; iCol < cCols ; iCol++ ){
	      sOutput += aiKnapsack[iRow][iCol] + "";
	     }
	     sOutput += "\n";
	    }
	    return sOutput;
	   }

	   
	   public static void main2(String args[]) {
	    int cRows = 2, cCols = 2;
	    int[][] aiKnapsack = null;
	    int[][] aiRectangles = new int[4][2];
	      
	    aiRectangles[0][0] = 1;
	    aiRectangles[0][1] = 1;
	    aiRectangles[1][0] = 1;
	    aiRectangles[1][1] = 1;
	    aiRectangles[2][0] = 1;
	    aiRectangles[2][1] = 1;
	    aiRectangles[3][0] = 1;
	    aiRectangles[3][1] = 1;
	    
	    aiKnapsack = insertIntoKnapsack( cRows, cCols, aiRectangles );
	    if( aiKnapsack != null )
	     System.out.println( getKnapsackString( aiKnapsack ) );
	    else
	     System.out.println( "Could not insert rectangles into knapsack" );
	   }

	//   public static void main(String args[]) {
//	    int cRows = 4, cCols = 4;
//	    int[][] aiKnapsack = null;
//	    int[][] aiRectangles = new int[5][2];
	//    
//	      
//	    aiRectangles[0][0] = 2;
//	    aiRectangles[0][1] = 2;
//	    aiRectangles[1][0] = 1;
//	    aiRectangles[1][1] = 3;
//	    aiRectangles[2][0] = 3;
//	    aiRectangles[2][1] = 1;
//	    aiRectangles[3][0] = 3;
//	    aiRectangles[3][1] = 1;
//	    aiRectangles[4][0] = 1;
//	    aiRectangles[4][1] = 3;
	//    
//	    aiKnapsack = insertIntoKnapsack( cRows, cCols, aiRectangles );
//	    if( aiKnapsack != null )
//	     System.out.println( getKnapsackString( aiKnapsack ) );
//	    else
//	     System.out.println( "Could not insert rectangles into knapsack" );
	//   }
	//
	//   public static void main(String args[]) {
//	    int cRows = 2, cCols = 2;
//	    int[][] aiKnapsack = null;
//	    int[][] aiRectangles = new int[4][2];
//	      
//	    aiRectangles[0][0] = 1;
//	    aiRectangles[0][1] = 1;
//	    aiRectangles[1][0] = 1;
//	    aiRectangles[1][1] = 1;
//	    aiRectangles[2][0] = 1;
//	    aiRectangles[2][1] = 1;
//	    aiRectangles[3][0] = 1;
//	    aiRectangles[3][1] = 1;
	//    
//	    aiKnapsack = insertIntoKnapsack( cRows, cCols, aiRectangles );
//	    if( aiKnapsack != null )
//	     System.out.println( getKnapsackString( aiKnapsack ) );
//	    else
//	     System.out.println( "Could not insert rectangles into knapsack" );
//	    /*
//	    12
//	    34
//	    */
	//   }

	//   public static void main(String args[]) {
//	    int cRows = 2, cCols = 10;
//	    int[][] aiKnapsack = null;
//	    int[][] aiRectangles = new int[5][2];
	//    
//	      
//	    aiRectangles[0][0] = 2;
//	    aiRectangles[0][1] = 2;
//	    aiRectangles[1][0] = 2;
//	    aiRectangles[1][1] = 4;
//	    aiRectangles[2][0] = 2;
//	    aiRectangles[2][1] = 1;
//	    aiRectangles[3][0] = 1;
//	    aiRectangles[3][1] = 1;
//	    aiRectangles[4][0] = 1;
//	    aiRectangles[4][1] = 3;
	//    
//	    aiKnapsack = insertIntoKnapsack( cRows, cCols, aiRectangles );
//	    if( aiKnapsack != null )
//	     System.out.println( getKnapsackString( aiKnapsack ) );
//	    else
//	     System.out.println( "Could not insert rectangles into knapsack" );
//	    /*
//	    1122223400
//	    1122223555
//	    */
	//   }
	   
	//   public static void main(String args[]) {
//	    int cRows = 4, cCols = 4;
//	    int[][] aiKnapsack = null;
//	    int[][] aiRectangles = new int[5][2];
	//    
//	      
//	    aiRectangles[0][0] = 2;
//	    aiRectangles[0][1] = 2;
//	    aiRectangles[1][0] = 1;
//	    aiRectangles[1][1] = 3;
//	    aiRectangles[2][0] = 3;
//	    aiRectangles[2][1] = 1;
//	    aiRectangles[3][0] = 3;
//	    aiRectangles[3][1] = 1;
//	    aiRectangles[4][0] = 1;
//	    aiRectangles[4][1] = 3;
	//    
//	    aiKnapsack = insertIntoKnapsack( cRows, cCols, aiRectangles );
//	    if( aiKnapsack != null )
//	     System.out.println( getKnapsackString( aiKnapsack ) );
//	    else
//	     System.out.println( "Could not insert rectangles into knapsack" );
//	    /*
//	    2223
//	    4113
//	    4113
//	    4555
//	    */
	//   }


	   
	//   public static void main(String args[]) {
//	    int cRows = 4, cCols = 8;
//	    int[][] aiKnapsack = null;
//	    int[][] aiRectangles = new int[7][2];
	//    
//	      
//	    aiRectangles[0][0] = 2;
//	    aiRectangles[0][1] = 3;
//	    aiRectangles[1][0] = 1;
//	    aiRectangles[1][1] = 4;
//	    aiRectangles[2][0] = 2;
//	    aiRectangles[2][1] = 1;
//	    aiRectangles[3][0] = 1;
//	    aiRectangles[3][1] = 1;
//	    aiRectangles[4][0] = 1;
//	    aiRectangles[4][1] = 2;
//	    aiRectangles[5][0] = 1;
//	    aiRectangles[5][1] = 5;
//	    aiRectangles[6][0] = 1;
//	    aiRectangles[6][1] = 6;
	//    
//	    aiKnapsack = insertIntoKnapsack( cRows, cCols, aiRectangles );
//	    if( aiKnapsack != null )
//	     System.out.println( getKnapsackString( aiKnapsack ) );
//	    else
//	     System.out.println( "Could not insert rectangles into knapsack" );
//	    /*
//	    11122223
//	    11145503
//	    66666000
//	    77777700
//	    */
	//   }
	//   
	   public static void main(String args[]) {
	    int cRows = 7, cCols = 5;
	    int[][] aiKnapsack = null;
	    int[][] aiRectangles = new int[8][2];
	    
	      
	    aiRectangles[0][0] = 1;
	    aiRectangles[0][1] = 5;
	    aiRectangles[1][0] = 1;
	    aiRectangles[1][1] = 4;
	    aiRectangles[2][0] = 2;
	    aiRectangles[2][1] = 1;
	    aiRectangles[3][0] = 1;
	    aiRectangles[3][1] = 1;
	    aiRectangles[4][0] = 1;
	    aiRectangles[4][1] = 2;
	    aiRectangles[5][0] = 3;
	    aiRectangles[5][1] = 2;
	    aiRectangles[6][0] = 1;
	    aiRectangles[6][1] = 3;
	    aiRectangles[7][0] = 2;
	    aiRectangles[7][1] = 3;
	    
//	    aiRectangles[0][0] = 2;
//	    aiRectangles[0][1] = 3;
//	    aiRectangles[1][0] = 1;
//	    aiRectangles[1][1] = 4;
//	    aiRectangles[2][0] = 2;
//	    aiRectangles[2][1] = 1;
//	    aiRectangles[3][0] = 1;
//	    aiRectangles[3][1] = 1;
//	    aiRectangles[4][0] = 1;
//	    aiRectangles[4][1] = 2;
//	    aiRectangles[5][0] = 1;
//	    aiRectangles[5][1] = 5;
//	    aiRectangles[6][0] = 1;
//	    aiRectangles[6][1] = 3;
//	    aiRectangles[7][0] = 3;
//	    aiRectangles[7][1] = 2;
	    
	    aiKnapsack = insertIntoKnapsack( cRows, cCols, aiRectangles );
	    if( aiKnapsack != null )
	     System.out.println( getKnapsackString( aiKnapsack ) );
	    else
	     System.out.println( "Could not insert rectangles into knapsack" );
	    /*
	    11134
	    11130
	    22220
	    55088
	    77788
	    00088
	    66666
	     
	     */

	   }
	   
	 
	}
